本週目標

進入挑戰的第二週了，這週的單元為"Tree"，理解二元樹結構與其前/中/後序遍歷邏輯，以及學習二元樹搜索演算法，包含：

• Quick Sort
• Merge Sort
• Tree Sort

今日學習二元樹的前/中/後序遍歷，馬上進入到筆記的部分。

二元樹：前/中/後序遍歷

學習影片:https://www.youtube.com/watch?v=7FpkEAYTIZI

前序遍歷（Preorder Traversal）

遞歸順序：根節點 -> 左子樹 -> 右子樹 [立馬印]
這種遍歷的重點是首先訪問根節點，再依次訪問左右子樹。

def preorder_traversal(node):
    if node:
        print(node.val)  # 訪問根節點
        preorder_traversal(node.left)  # 遍歷左子樹
        preorder_traversal(node.right)  # 遍歷右子樹

中序遍歷（Inorder Traversal）

遞歸順序：左子樹 -> 根節點 -> 右子樹 [左邊印回來]
中序遍歷最常用於排序樹的節點，因為訪問順序與數值大小的順序一致。

def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)  # 遍歷左子樹
        print(node.val)  # 訪問根節點
        inorder_traversal(node.right)  # 遍歷右子樹

後序遍歷（Postorder Traversal）

遞歸順序：左子樹 -> 右子樹 -> 根節點 [右邊印回來]
在後序遍歷中，根節點最後被訪問，適合用於刪除樹或計算節點。

def postorder_traversal(node):
    if node:
        postorder_traversal(node.left)  # 遍歷左子樹
        postorder_traversal(node.right)  # 遍歷右子樹
        print(node.val)  # 訪問根節點

以上為 DFS Left 方式的前/中/後序遍歷，如果是 DFS Right 則完全反過來，Inorder Traversal會變為[右邊印回來]，Postorder Traversal會變為左邊印回來。

影片還提到 BST（Binary Search Tree，二元搜索樹），它是一種每個節點的左子樹節點都比根節點小，而右子樹節點都比根節點大的樹結構，這樣的特性讓 BST 特別適合用於查找、插入和刪除操作，因為這些操作的平均時間複雜度為 O(log n)。

小結

在學習到這個單元之前，我完全記不起來這三種不同遍歷模式的名稱和邏輯，透過教學影片的解說，結合程式碼的實際操作，我逐漸理解了它們之間的差異。前序遍歷（Preorder Traversal）優先處理根節點；中序遍歷（Inorder Traversal）則依序處理左子樹、根節點、右子樹，特別適合用於排序操作；後序遍歷（Postorder Traversal）則是最後處理根節點，非常適合刪除或處理樹結構中的節點。